Scanning of semiconductor layouts is used in layout processing or modification systems that migrate a layout to another technology, systems that make the layout smaller or systems that try to fix violations of constraints in these layouts. A layout migration system tries to calculate a new layout, based on an input layout, such that the new layout fulfills the design rules or constraints of the new production process for the semiconductor device. Layout compaction systems try to optimize a design or layout for area. The footprint of the layout has to become smaller and a compaction engine can do this such that the original design intent is still in the new layout and such that no design rule violations appear.
A two dimensional compaction system is known from U.S. Pat. No. 6,587,992. In the system according to that US patent, position variables of edges and corner points of layout elements are determined and a system of constraints is constructed. The constraints describe minimum distances between edges and corners of two layout elements in the terms of position variables. Some constraints are one dimensional (e.g. x2−x1>d) other constraints are two-dimensional (e.g. (x2−x1)2+(y2−x1)2>d2). An objective function is established that must be optimized for the two dimensional compaction. The system of constraints is solved to compact and optimize the layout in two dimensions simultaneously. Due to the non-linear two-dimensional constraints, the system of constraints is very difficult to solve in a reasonable runtime. Therefore the non-linear constraints are represented by linear constraints (e.g. (x2−x1)+(y2−y1)>d√{square root over (2)}).
It is a problem of known systems that, in a layout with n elements, moving freedom in 2 dimensions results in n2 constraints. In theory every object can move close to every other object and therefore one has to constraint every object to every other object. For larger layouts, the number of constraints will severely increase the time needed for solving the system of constraints.